import { Vec2 } from './geometry'
/**
 * 求凸包
 * @date 2023/12/4 - 15:19:23
 *
 * @param {Vec2[]} points
 * @returns {{}}
 */
export function getConvexHull (points: Vec2[]) {
  if (points.length < 3) {
    return []
  }

  points.sort((a: Vec2, b: Vec2) => {
    if (a.x !== b.x) {
      return a.x < b.x ? -1 : 1
    }

    if (a.y !== b.y) {
      return a.y < b.y ? -1 : 1
    }

    return 0
  })

  let convex: Vec2[] = []
  convex.push(points[0])
  convex.push(points[1])
  for (let i = 2; i < points.length; i++) {
    tryPoint(convex, 1, points[i])
  }

  let offset = convex.length
  convex.push(points[points.length - 2])
  for (let i = points.length - 3; i >= 0; i--) {
    tryPoint(convex, offset, points[i])
  }

  return convex
}

function tryPoint (convex: Vec2[], offset: number, c: Vec2) {
  while (convex.length > offset) {
    let a = convex[convex.length - 2]
    let b = convex[convex.length - 1]
    if (turnLeft(a, b, c)) {
      convex.push(c)
      break
    }

    convex.pop()
  }

  if (convex.length === offset) {
    convex.push(c)
  }
}

export function turnLeft (a: Vec2, b: Vec2, c: Vec2) {
  let v1 = b.sub(a)
  let v2 = c.sub(b)
  let cross = v1.cross(v2)
  return cross > 0 ? true : cross === 0 ? v1.dot(v2) > 0 : false
}

/**
 * 求凸包2 -- 光照法
 * @date 2023/12/21 - 15:11:23
 *
 * @param {Vec2[]} points
 * @returns {{}}
 */
export function getConvexHull2 (points: Vec2[]) {
  let convex: Vec2[] = [points[0], points[1], points[2], points[0]]
  if (points[1].sub(points[0]).cross(points[2].sub(points[1])) < 0) {
    convex = [points[2], points[1], points[0], points[2]]
  }
  for (let i = 3; i < points.length; i++) {
    let indices: number[] = []
    for (let j = 0; j < convex.length - 1; j++) {
      let edge = convex[j + 1].sub(convex[j])
      let vec = points[i].sub(convex[j])
      if (Vec2.turnRight(edge, vec)) {
        indices.push(j + 1)
      }
    }

    if (indices.length == 0) {
      continue
    }

    // 以下2种情况直接替换indices.length - 1个点
    // 1. 只有一个点
    // 2. 不跨越首点
    if (
      indices.length === 1 ||
      indices[0] !== 1 ||
      indices[indices.length - 1] !== convex.length - 1
    ) {
      convex.splice(indices[0], indices.length - 1, points[i])
      continue
    }

    // 跨越首点的情况, 例如: 1, 4, 5
    let k = 0
    for (; k < indices.length - 1; k++) {
      if (indices[k + 1] - indices[k] !== 1) {
        break
      }
    }
    convex.splice(0, 1, points[i])
    convex.splice(indices[k + 1], indices.length - k - 2)
    convex.splice(indices[0], k)
    convex[convex.length - 1] = convex[0]
  }
  return convex
}
